package DMSXL._2024.BinaryTrees;

public class lowestCommonAncestor_selected {
    public static void main(String[] args) {

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //说明已经找到一个节点了，先找到的一定是父节点
        if(root == null || root.val == p.val || root.val == q.val){
            return root;
        }
        //判断是否在一边，下面这个说明在root两边。
        if((p.val < root.val && q.val > root.val)||(p.val > root.val && q.val < root.val)){
            return root;
        }

        //在一边看看往哪边遍历
        if(p.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        else {
            return lowestCommonAncestor(root.right,p,q);
        }
    }
}
